package com.ycz.algorithm.utils.graph.adjacencylist;

import java.util.*;

/**
 * @author yancz
 * @ClassName AdjacencyList
 * @description: // 基于邻接表的图及常用操作
 * @date 2025-01-09 16:01:57
 * @version: 1.0
 */
public class AdjacencyList {

    // key作为顶点，value作为邻接表
    public Map<Vertex, Set<Vertex>> adjList;

    /*
     * @author yancz
     * @description // 构造方法
     * @date 2025/1/10 11:52
     * @param edges 边二维数组，{(a,b),(c,d),(e,f)}，(a,b)代表顶点a和顶点b之间的边
     * @return null
     */
    public AdjacencyList(Vertex[][] edges) {
        this.adjList = new HashMap<>();
        for (Vertex[] edge : edges) {
            addVertex(edge[0]); // 添加顶点
            addVertex(edge[1]);
            addEdge(edge[0], edge[1]); // 添加边
        }
    }

    // 获取顶点数量
    int size() {
        return adjList.size();
    }

    /*
     * @author yancz
     * @description // 添加边
     * @date 2025/1/10 11:40
     * @param v1 顶点
     * @param v2 顶点2
     * @return void
     */
    void addEdge(Vertex v1, Vertex v2) {
        if (!adjList.containsKey(v1) || !adjList.containsKey(v2) || v1 == v2) {
            throw new IllegalArgumentException("非法参数！");
        }
        adjList.get(v1).add(v2); // 添加边v1-v2
        adjList.get(v2).add(v1); // 添加边v2-v1
    }

    // 删除边
    void removeEdge(Vertex v1, Vertex v2) {
        if (!adjList.containsKey(v1) || !adjList.containsKey(v2) || v1 == v2) {
            throw new IllegalArgumentException("非法参数！");
        }
        adjList.get(v1).remove(v2); // 删除边v1-v2
        adjList.get(v2).remove(v1); // 删除边v2-v1
    }

    /*
     * @author yancz
     * @description // 添加不重复的顶点
     * @date 2025/1/10 11:47
     * @param vertex 顶点
     * @return void
     */
    void addVertex(Vertex vertex) {
        if (adjList.containsKey(vertex)) return;
        adjList.put(vertex, new HashSet<>());
    }


    // 删除顶点
    void removeVertex(Vertex vertex) {
        if (!adjList.containsKey(vertex)) throw new IllegalArgumentException("顶点不存在！");
        adjList.remove(vertex); // 移除顶点对应的列表
        // 遍历其他顶点的列表，删除包含待删除顶点的边
        for (Set<Vertex> list : adjList.values()) {
            list.remove(vertex);
        }
    }

    // 打印邻接表
    public void commonPrint() {
        System.out.println("邻接表：");
        for (Map.Entry<Vertex, Set<Vertex>> entry : adjList.entrySet()) {
            Set<Vertex> values = entry.getValue();
            List<Integer> list = Vertex.vertexToList(new ArrayList<>(values));
            System.out.println(entry.getKey().val + " -> " + list);
        }
        System.out.println("------------------------");
    }

    public static void main(String[] args) {
        // 每个Vertex实例对象代表一个顶点
        Vertex a = new Vertex(1);
        Vertex b = new Vertex(2);
        Vertex c = new Vertex(3);
        Vertex d = new Vertex(4);
        Vertex e = new Vertex(5);
        // 构建二维数组
        Vertex[][] edges = {
                {a, c}, {a, e}, // 边1-3，边1-5
                {c, a}, {c, b}, // 边3-1，边3-2
                {b, c}, {b, e}, // 边2-3，边2-5
                {e, a}, {e, b}, // 边5-1，边5-2
                {d, b}, {d, e} // 边4-2，边4-5
        };
        AdjacencyList adjacencyList = new AdjacencyList(edges);
        adjacencyList.commonPrint();
        // 添加边1-2
        adjacencyList.addEdge(a, b);
        adjacencyList.commonPrint();
        // 删除边1-3
        adjacencyList.removeEdge(a, c);
        adjacencyList.commonPrint();
        // 添加顶点6
        Vertex f = new Vertex(6);
        adjacencyList.addVertex(f);
        adjacencyList.commonPrint();
        // 删除顶点3
        adjacencyList.removeVertex(c);
        adjacencyList.commonPrint();
    }

}
